package com.practice.zuocy.base.class09;

import java.util.HashSet;

/*
 * 贪心算法求解的标准过程（TODO：在刷题中不用）：
 * （1）分析业务
 * （2）根据业务逻辑找到不同的贪心策略
 * （3）对于能举出反例的策略直接跳过，不能举出反例的策略要证明有效性。这往往是特别困难的，要求数学能力很高且不具统一的技巧性
 */

/*
 * 贪心算法的解题套路：
 * （1）实现一个不依靠贪心策略的解法x，可以用最暴力的尝试（比如全排列等等）
 * （2）脑补出贪心策略A、贪心策略B、贪心策略C...
 * （3）用解法x和对数器，用实验的方式得知哪个贪心策略正确
 * （4）不要去纠结贪心策略的证明
 */


/**
 * 【题目】：
 * 给定一个字符串str（可以认为是一条街道），只由'x'和'.'两种字符构成。
 * 'x'表示墙，不能放灯，也不需要点亮
 * '.'表示居民点，可以放灯，需要点亮
 * 如果灯放在i位置，可以让i-1，i和i+1三个位置被点亮
 * 返回如果点亮str中所有需要点亮的位置，至少需要几盏灯。
 */
public class Code02_Light {

	/**
	 * 暴力解（全部枚举）
	 * @param road
	 * @return
	 */
	public static int minLight1(String road) {
		if (road == null || road.length() == 0) {
			return 0;
		}
		return process(road.toCharArray(), 0, new HashSet<>());
	}

	// str[index....]位置，自由选择放灯还是不放灯
	// str[0..index-1]位置呢？已经做完决定了，那些放了灯的位置，存在lights里
	// 要求选出能照亮所有'.'的方案，并且在这些有效的方案中，返回最少需要几盏灯
	public static int process(char[] str, int index, HashSet<Integer> lights) {
		if (index == str.length) { // 结束的时候（来到了终止位置，没有位置可以放灯了）
			// 验证目前收集到的这种方案能不能把所有位置照亮
			for (int i = 0; i < str.length; i++) {
				if (str[i] != 'X') { // 当前位置是点的话
					// 查看i、i-1、i+1位置是否有灯
					if (!lights.contains(i - 1) 
							&& !lights.contains(i) 
							&& !lights.contains(i + 1)) {
						// 无效的方案，返回系统最大值
						return Integer.MAX_VALUE;
					}
				}
			}
			// 返回有效的等的数量
			return lights.size();
		} else { // str还没结束
			// 当前的index位置，不管是‘X’还是‘.’，都有一个选择就是当前位置不放灯，直接跳到index + 1位置。不放灯的结果用no变量做记录
			int no = process(str, index + 1, lights);
			int yes = Integer.MAX_VALUE;
			if (str[index] == '.') {//只有当前的index位置是‘.’时才能选择放灯
				// 选择在index位置放灯，放灯的结果用yes变量做记录
				lights.add(index);
				yes = process(str, index + 1, lights);
				// 选择在index位置不放灯（因为始终在用一个lights在运转代码（没有克隆新的），所有需要恢复现场（避免脏数据））
				lights.remove(index);
			}
			// 选择放灯数小的方案
			return Math.min(no, yes);
		}
	}

	/**
	 * 贪心解法
	 * (当前的index位置不会被之前的位置影响到（不会因为之前放的灯，导致当前index位置是亮的状态）)
	 * @param road
	 * @return
	 */
	public static int minLight2(String road) {
		char[] str = road.toCharArray();
		// 从0位置出发
		int index = 0;
		// 当前灯的数量
		int light = 0;
		while (index < str.length) {
			if (str[index] == 'X') {
				// inde位置是'x'，不放灯也不需要照亮，index++。
				index++;
			} else { // index位置是 `.`
				// 一定会放灯
				light++;
				if (index + 1 == str.length) {// 下面没有字符了
					break;
				} else {
					if (str[index + 1] == 'X') {
						// index位置是'.'，index+1位置是'x'。我们在index位置放灯后，跳到index+2位置去做决定
						index = index + 2;
					} else {
						// index位置是'.'，index+1位置是'.'。不管index+2位置是什么，都会在index+1位置放一盏灯，跳到index+3处去做决定
						index = index + 3;
					}
				}
			}
		}
		// 返回总等数
		return light;
	}

	// for test
	public static String randomString(int len) {
		char[] res = new char[(int) (Math.random() * len) + 1];
		for (int i = 0; i < res.length; i++) {
			res[i] = Math.random() < 0.5 ? 'X' : '.';
		}
		return String.valueOf(res);
	}

	public static void main(String[] args) {
		int len = 20;
		int testTime = 100000;
		for (int i = 0; i < testTime; i++) {
			String test = randomString(len);
			int ans1 = minLight1(test);
			int ans2 = minLight2(test);
			if (ans1 != ans2) {
				System.out.println("oops!");
			}
		}
		System.out.println("finish!");
	}
}
